package 程序员面试金典;

import java.util.Map;

public class 直方图的水量 {

    public int trap(int[] height) {
        if (height.length<2)
            return 0;
       //先倒叙遍历，找到每个位置其右侧的最大值
        int right=0;
        int[] maxleft = new int[height.length];
        for (int i = height.length-1; i >=0 ; i--) {
            maxleft[i]=right;
            right=Math.max(right,height[i]);
        }
        int left=height[0];
        //统计水量
        int sum=0;
        //找到当前位置左侧的最大值
        for (int i = 1; i < height.length; i++) {
            int c = Math.min(left, maxleft[i]) - height[i];
            sum+= c<=0 ? 0 : c;
            left=Math.max(left,height[i]);
        }
        return sum;
    }
}
